昨天介紹了 陣列 和 矩陣，今天來介紹也很常見的 鏈結串列 (Linked List)。

Linked List 也有分成幾種：

• 單向鏈結串列 (Singly Linked List)
• 雙向鏈結串列 (Doubly Linked List)
• 循環鏈結串列 (Circular Linked List)
  • 可以單向也可以雙向

單向鏈接串列 (Singly Linked List)

Linked List 大概長下面這樣：

每一個 Data 區塊 + Next 區塊 稱為一個 Node (節點) 作用如下：

而最前面的 Head 會指向第一個 Node，但是 Head 不是一個 Node，所以不會有資料
而最後面的 Tail 會指向最後一個 Node，但是 Tail 不是一個 Node，所以不會有資料

參考程式碼

首先可以先定義 Node

class Node:
    def __init__(self, data):
        self.data = data  # 資料
        self.next = None  # 指向下一個節點

再來就可以建立 Linked List 的資料結構

class LinkedList:
    def __init__(self):
        self.head = None # Head 存放第一個 Node 的位置
        self.tail = None # Tail 存放最後一個 Node 的位置

但目前這個 Linked List 裡面並沒有任何的 Node 所以我們 需要加入 (append)

    # 這裡的 append 跟 python list 一樣都是從最後面加入
    def append(self, data):
        new_node = Node(data)
        if not self.head:  # 如果 Liked List 為空，將 Head、Tail 指向新 Node
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node  # 如果非空就直接用 tail 連接
        self.tail = new_node       # 更新 tail

現在想要從最前面加入 (prepend) 則需要

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head # 先把 Head 加入 next
        self.head = new_node      # 再把新 Node 設為 Head
        if self.tail is None:  # 如果 Linked List 原本為空
            self.tail = new_node

如果要從中間某個節點後插入 (Insert)

    def insert(self, pivot_node, data):
        if pivot_node is None:
            raise ValueError("pivot_node 不能是 None")

        # 將新的 Node 加到選定的 Node 的後面
        new_node = Node(data)
        new_node.next = pivot_node.next
        pivot_node.next = new_node

        if self.tail == pivot_node: # 如果插入在尾端，要更新 tail
            self.tail = new_node

再來想 刪除 (Delete) 的話

    def delete(self, node):
        if node is None: # 不能刪除空的
            return

        # 如果刪除的是 head
        if self.head == node:
            self.head = node.next
            if self.head is None:  # 如果刪完 Linked List 為空
                self.tail = None
            return

        # 尋找前一個節點，需要從頭開始
        prev = self.head
        while prev and prev.next != node:
            prev = prev.next

        if prev is None: # 沒找到該節點，可能 Linked List 有問題
            return

        prev.next = node.next

        if node == self.tail:  # 如果刪掉的是尾端
            self.tail = prev
            
        node.next = None # 清除與 Linked List 的關係

那這裡就可以發現，單向鏈結串列 在做 Delete 的時候需要從頭開始找前一個 Node，會需要 O(N)，所以就出現了雙 向鏈結串列 (Doubly Linked List)

雙向鏈結串列 (Doubly Linked List)

每個 Node 除了 Next，還多了一個 Prev，可以指回上一個節點，這樣刪除時就不用再從頭找前一個節點。

參考程式碼

class DNode:
    def __init__(self, data):
        self.data = data
        self.next = None  # 指向下一個節點
        self.prev = None  # 指回上一個節點

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail  # 多一個 Prev
        self.tail = new_node

    def prepend(self, data):
        new_node = DNode(data)
        if not self.head:  
            self.head = new_node
            self.tail = new_node
            return
        new_node.next = self.head
        self.head.prev = new_node  # 舊 Head 的 Prev 指向新 Node
        self.head = new_node       # 再把新 Node 設成 Head

    def insert_after(self, pivot_node, data):
        if pivot_node is None:
            raise ValueError("pivot_node 不能是 None")

        new_node = DNode(data)
        new_node.next = pivot_node.next
        new_node.prev = pivot_node
        if pivot_node.next:  # 如果不是尾端
            pivot_node.next.prev = new_node
        pivot_node.next = new_node

        if self.tail == pivot_node:  # 如果插在尾端，要更新 tail
            self.tail = new_node

    def delete(self, node):  # 雙向的不需要從頭開始找，只要 O(1)
        if node is None:
            return

        if node == self.head:  # 如果刪的是頭
            self.head = node.next
            if self.head:  # 如果還有下一個
                self.head.prev = None
            else:  # 如果刪完空了
                self.tail = None
                
        elif node == self.tail:  # 如果刪的是尾
            self.tail = node.prev
            if self.tail:
                self.tail.next = None
                
        else:  # 中間的 node
            node.prev.next = node.next
            node.next.prev = node.prev

        node.next = None
        node.prev = None

🔹 循環鏈結串列 (Circular Linked List)

循環鏈結串列 (Circular Linked List) 就是把頭尾連起來，有單向跟雙向

單向

單向的就是最後一個 Node 的 Next 會指向第一個 Node，整個串列首尾相接。

雙向

雙向的就是多了 Prev，最後一個 Node 的 Prev 會指向第一個 Node

參考程式碼

單向

class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:  # 如果空的
            self.head = new_node
            self.tail = new_node
            new_node.next = new_node  # 自己指自己
            return
        self.tail.next = new_node
        new_node.next = self.head  # 新 Node 指回 Head
        self.tail = new_node

    def prepend(self, data):
        new_node = Node(data)
        if not self.head:  # 如果空的
            self.head = new_node
            self.tail = new_node
            new_node.next = new_node
            return
        new_node.next = self.head
        self.head = new_node
        self.tail.next = self.head  # Tail 重新指回新的 Head

    def delete(self, data):
        if not self.head:
            return

        curr = self.head
        prev = self.tail
        while True:
            if curr.data == data:  # 找到要刪的節點
                if curr == self.head:  # 刪頭
                    self.head = curr.next
                    self.tail.next = self.head
                elif curr == self.tail:  # 刪尾
                    self.tail = prev
                    self.tail.next = self.head
                else:  # 中間
                    prev.next = curr.next
                return
            prev = curr
            curr = curr.next
            if curr == self.head:  # 整圈都沒找到
                break

雙向 (ChatGPT)

class DoublyCircularLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head: 
            self.head = new_node
            self.tail = new_node
            new_node.next = new_node
            new_node.prev = new_node
            return
        
        new_node.prev = self.tail
        new_node.next = self.head
        self.tail.next = new_node
        self.head.prev = new_node
        self.tail = new_node

    def prepend(self, data):
        new_node = Node(data)
        if not self.head:  
            self.head = new_node
            self.tail = new_node
            new_node.next = new_node
            new_node.prev = new_node
            return
        
        new_node.next = self.head
        new_node.prev = self.tail
        self.head.prev = new_node
        self.tail.next = new_node
        self.head = new_node

    def delete(self, data):
        if not self.head:
            return

        curr = self.head
        while True:
            if curr.data == data:
                if curr == self.head and curr == self.tail:  
                    self.head = None
                    self.tail = None
                elif curr == self.head:  
                    self.head = curr.next
                    self.head.prev = self.tail
                    self.tail.next = self.head
                elif curr == self.tail:  
                    self.tail = curr.prev
                    self.tail.next = self.head
                    self.head.prev = self.tail
                else:  
                    curr.prev.next = curr.next
                    curr.next.prev = curr.prev
                return
            curr = curr.next
            if curr == self.head:  
                break

此外，這個資料結構並不是固定的，可以依據需求增加功能，像是這裡的例子就都沒有很重要的 find。

謝謝~

參考資料
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein，《演算法導論》，碁峰資訊，2024 年
ChatGPT